package leetcode_100;

import java.util.ArrayList;
import java.util.List;

/**
 *@author 周杨
 *Subsets_78 给定一个没有重复数字的数组 返回所有其中数字的组合 没有个数限制
 *describe: 用回溯 AC 14%
 *2018年5月14日 上午9:46:48
 */
public class Subsets_78 {
	List<List<Integer>> res;
	int nums[];
	public static void main(String[] args) {
		Subsets_78 test=new Subsets_78();
		Object res = test.subsets(new int[] {5,1,2,3});
	}
	
	public List<List<Integer>> subsets_(int[] nums) {
		List<List<Integer>> res =new ArrayList<List<Integer>>();
		List<Integer> init=new ArrayList<Integer>();
		res.add(init);
		for(int i=0;i<nums.length;++i) {
			int size=res.size();
			for(int j=0;j<size;++j) {
				List<Integer> now=res.get(j);
				List<Integer> temp=new ArrayList<Integer>();
				temp.addAll(now);
				temp.add(nums[i]);
				res.add(temp);
			}
		}
		return res;
	}
	
    public List<List<Integer>> subsets(int[] nums) {
        this.res=new ArrayList<List<Integer>>();
        this.nums=nums;
        this.res.add(new ArrayList<Integer>());
        for(int i=1;i<=nums.length;++i) {//最多取i个数
        	help(new ArrayList<Integer>(),-1,i);
        }
    	return this.res;
    }
    
    public void help(List<Integer> list,int top,int count) {
    	for(int i=top+1;i<this.nums.length;++i) {
			list.add(this.nums[i]);
			if(list.size()==count) {//满了
				List<Integer> now=new ArrayList<Integer>();
				now.addAll(list);
				this.res.add(now);
				}
			else
				 help(list,i,count);
			list.remove(list.size()-1);
		}
    	
    }

}
